import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 139. Word Break 单词拆分
 * https://leetcode-cn.com/problems/word-break/
 */
class WordBreak {
    /**
     * 方法： 使用动态规划判断字符串是否可以被拆分成字典中的单词
     *       f[i]表示字符串s的前i个字符是否可以被拆分
     *       对于每个位置i，枚举最后一个单词的起始位置j
     *       如果f[j]为真且s[j:i]在字典中，则f[i]为真
     *
     * Args:
     *      s: String - 需要判断的字符串
     *      wordDict: List<String> - 包含可用单词的字典
     *
     * Returns:
     *      boolean: 字符串是否可以被拆分成字典中的单词
     *
     * Time: O(n * m) - 其中n是字符串长度，m是字典中最长单词的长度
     *
     * Space: O(n) - 需要一个长度为n的数组存储动态规划状态
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int maxLen = 0;
        for(String word : wordDict){
            maxLen = Math.max(maxLen, word.length());
        }
        Set<String> words = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] f = new boolean[n + 1];
        f[0] = true; //空字符串
        for(int i = 1; i <=n; i++){
            for(int j = i -1; j >= Math.max(i - maxLen, 0); j--){
                if(f[j] && words.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n];
    }

    /**
     * 方法： 使用记忆化搜索判断字符串是否可以被拆分成字典中的单词
     *       自顶向下递归，记录每个位置是否可以被拆分
     *       对于每个位置i，枚举最后一个单词的起始位置j
     *       如果s[j:i]在字典中且j位置可以被拆分，则i位置可以被拆分
     *
     * Args:
     *      i: int - 当前处理到的字符串位置
     *      maxLen: int - 字典中最长单词的长度
     *      s: String - 需要判断的字符串
     *      words: Set<String> - 包含可用单词的字典
     *      memo: int[] - 记忆化数组,记录每个位置是否可以被拆分
     *
     * Returns:
     *      int: 1表示可以被拆分,0表示不可以被拆分
     *
     * Time: O(n * m) - 其中n是字符串长度，m是字典中最长单词的长度
     * 最坏情况下 O(n^2 * maxLen)
     *
     * Space: O(n) - 需要一个长度为n的数组存储记忆化状态
     */
    public boolean wordBreak1(String s, List<String> wordDict) {
        int maxLen = 0;
        for(String word : wordDict){
            maxLen = Math.max(maxLen, word.length());
        }
        Set<String> words = new HashSet<>(wordDict);
        int n = s.length();
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return dfs(n, maxLen, s, words, memo) == 1;
    }

    private int dfs(int i, int maxLen, String s, Set<String> words, int[] memo){
        if(i == 0){
            return 1;
        }
        if(memo[i] != -1){
            return memo[i];
        }
        for(int j = i-1; j >= Math.max(i-maxLen, 0); j--){
            if(words.contains(s.substring(j, i)) && dfs(j, maxLen, s, words, memo) == 1){
                return memo[i] = 1;
            }
        }
        return memo[i] = 0;
    }
}